package org.usmile.algorithms.leetcode.middle;

import org.usmile.algorithms.leetcode.ListNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 61. 旋转链表
 *
 * 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
 *
 * 示例 1：
 * 输入：head = [1,2,3,4,5], k = 2
 * 输出：[4,5,1,2,3]
 *
 * 示例 2：
 * 输入：head = [0,1,2], k = 4
 * 输出：[2,0,1]
 *
 * 提示：
 * 链表中节点的数目在范围 [0, 500] 内
 * -100 <= Node.val <= 100
 * 0 <= k <= 2 * 109
 */
public class _0061 {
}

class _0061_Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) {
            return head;
        }
        int len = 1;
        ListNode lastNode = head;
        while (lastNode.next != null) {
            len++;
            lastNode = lastNode.next;
        }
        if (k % len == 0) {
            return head;
        }
        k = k % len;
        ListNode newTail = head;
        for (int i = 0; i < len - k - 1; i++) {
            newTail = newTail.next;
        }

        ListNode newHead = newTail.next;
        newTail.next = null;
        lastNode.next = head;

        return newHead;
    }
}

class _0061_Solution1 {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) {
            return head;
        }
        int count = 0;
        ListNode curr = head;
        Map<Integer, ListNode> nodeMap = new HashMap<>();
        while (curr != null) {
            nodeMap.put(count, curr);
            count++;
            curr = curr.next;
        }

        k = k % count;
        if (k == 0) {
            return head;
        }

        ListNode[] nodes = new ListNode[count];
        for (Map.Entry<Integer, ListNode> entry : nodeMap.entrySet()) {
            nodes[(entry.getKey() + k) % count] = entry.getValue();
        }

        ListNode dummy = new ListNode();
        ListNode prev = dummy;
        for (int i = 0; i < count; i++) {
            prev.next = nodes[i];
            prev = prev.next;
        }

        prev.next = null;

        return dummy.next;
    }
}